#include <isa.h>

/* We use the POSIX regex functions to process regular expressions.
 * Type 'man regex' for more information about POSIX regex functions.
 */
#include <regex.h>

#include <memory/paddr.h>


void init_regex();
static bool make_token(char *e);
bool check_parentheses(int p ,int q);
int pir(int type);
int dominant_operator(int p , int q);
word_t eval(int p, int q);
word_t expr(char *e, bool *success);

enum {
  TK_NOTYPE = 256, TK_EQ,TK_UEQ,TK_logical_AND,TK_logical_OR,TK_logical_NOT,TK_hex,TK_number,TK_reg,NEG,DEREF

  /* TODO: Add more token types */

};

static struct rule {
  const char *regex;
  int token_type;
} rules[] = {

  /* TODO: Add more rules.
   * Pay attention to the precedence level of different rules.
   */

  {" +", TK_NOTYPE},        // spaces
  {"\\+", '+'},             // plus
  {"==", TK_EQ},            // equal
  {"\\(",'('},              // left parenthesis
  {"\\)",')'},              // right parenthesis
  {"\\+",'+'},              // plus
  {"-",'-'},                // subtraction
  {"\\*",'*'},              // multiplication
  {"/",'/'},                // division
  {"!=",TK_UEQ},            // unequal
  {"&&",TK_logical_AND},    //logical AND
  {"\\|\\|",TK_logical_OR}, //logical OR
  {"!",TK_logical_NOT},     //logical NOT
  {"0[xX][A-Fa-f0-9]{1,8}",TK_hex},  //hex
  {"[a-z0-9]{2,3}",TK_reg}, //reg
  {"[0-9]{1,10}",TK_number}  //number
  
};

#define NR_REGEX ARRLEN(rules)

static regex_t re[NR_REGEX] = {};

/* Rules are used for many times.
 * Therefore we compile them only once before any usage.
 */
void init_regex() {
  int i;
  char error_msg[128];
  int ret;

  for (i = 0; i < NR_REGEX; i ++) {
    ret = regcomp(&re[i], rules[i].regex, REG_EXTENDED);
    if (ret != 0) {
      regerror(ret, &re[i], error_msg, 128);
      panic("regex compilation failed: %s\n%s", error_msg, rules[i].regex);
    }
  }
}

typedef struct token {
  int type;
  char str[64];
} Token;

static Token tokens[32] __attribute__((used)) = {};
static int nr_token __attribute__((used))  = 0;

static bool make_token(char *e) {
  int position = 0;
  int i;
  regmatch_t pmatch;

  nr_token = 0;

  while (e[position] != '\0') {
    /* Try all rules one by one. */
    for (i = 0; i < NR_REGEX; i ++) {
      if (regexec(&re[i], e + position, 1, &pmatch, 0) == 0 && pmatch.rm_so == 0) {
        char *substr_start = e + position;
        int substr_len = pmatch.rm_eo;

        Log("match rules[%d] = \"%s\" at position %d with len %d: %.*s",
            i, rules[i].regex, position, substr_len, substr_len, substr_start);

        position += substr_len;

        /* TODO: Now a new token is recognized with rules[i]. Add codes
         * to record the token in the array `tokens'. For certain types
         * of tokens, some extra actions should be performed.
         */

        switch (rules[i].token_type) {
          case TK_NOTYPE: break;
          case TK_EQ: tokens[nr_token].type = TK_EQ;strcpy(tokens[nr_token].str,"==");break;
          case '(' : tokens[nr_token].type ='(';break;
          case ')' : tokens[nr_token].type =')';break;
          case '/' : tokens[nr_token].type ='/';break;
          case '+' : tokens[nr_token].type ='+';break;
          case '-' : tokens[nr_token].type ='-';break;
          case '*' : tokens[nr_token].type ='*';break;
          case TK_UEQ: tokens[nr_token].type = TK_UEQ;strcpy(tokens[nr_token].str,"!=");break;
          case TK_logical_AND : tokens[nr_token].type = TK_logical_AND;strcpy(tokens[nr_token].str,"&&");break;
          case TK_logical_OR : tokens[nr_token].type = TK_logical_OR;strcpy(tokens[nr_token].str,"||");break;
          case TK_logical_NOT: tokens[nr_token].type = TK_logical_NOT;strcpy(tokens[nr_token].str,"!");break;
          case TK_number: tokens[nr_token].type = TK_number;strncpy(tokens[nr_token].str,&e[position-substr_len],substr_len);break;
          case TK_reg: tokens[nr_token].type = TK_reg;strncpy(tokens[nr_token].str,&e[position-substr_len],substr_len);break;
          case TK_hex: tokens[nr_token].type = TK_hex;strncpy(tokens[nr_token].str,&e[position-substr_len],substr_len);break;
          default: nr_token--;break;
        }

        nr_token++;
        break;
      }
    }

    if (i == NR_REGEX) {
      printf("no match at position %d\n%s\n%*.s^\n", position, e, position, "");
      return false;
    }
  }
  nr_token--;

  for (i = 0; i < nr_token; i ++) {
    if(tokens[i].type == '*' && (i == 0 || (tokens[i - 1].type != TK_number && tokens[i-1].type!= TK_hex && tokens[i-1].type!= TK_reg && tokens[i-1].type!=')')) ) 
        tokens[i].type = DEREF;
    if(tokens[i].type == '-' && (i == 0 || (tokens[i - 1].type != TK_number && tokens[i-1].type!= TK_hex && tokens[i-1].type != TK_reg && tokens[i-1].type!=')')) ) 
        tokens[i].type = NEG;
  }


  return true;
}

bool check_parentheses(int p ,int q){
   // printf("--------------\n");  
    int i,tag = 0;
    if(tokens[p].type != '(' || tokens[q].type != ')') return false; //首尾没有()则为false 
    for(i = p ; i <= q ; i ++){    
        if(tokens[i].type == '(') tag++;
        else if(tokens[i].type == ')') tag--;
        if(tag == 0 && i < q) return false ;  //(3+4)*(5+3) 返回false
    }                              
    if( tag != 0 ) return false;   
    return true;                   
} 

int pir(int type){
  switch(type){
    case '*': return 9;
    case '/': return 9;
    case '+': return 10;
    case '-': return 10;
    default: return 0;
  }
}

int dominant_operator(int p , int q){
    int i ,dom = p, left_n = 0;
    int pr = -1 ;
    for(i = p ; i <= q ; i++){
        if(tokens[i].type == '('){
            left_n += 1;
            i++;
            while(1){
                if(tokens[i].type == '(') left_n += 1;
                else if(tokens[i].type == ')') left_n --;
                i++;
                if(left_n == 0){
                  i--;
                  break;
                }
            }  
            if(i > q)break;
        }      
        else if(tokens[i].type == TK_number) continue;
        else if( pir(tokens[i].type ) > pr){
            pr = pir(tokens[i].type);
            dom = i;
        }      
    }          
    //printf("dom:%d\n",dom);
    return dom;
}  

word_t eval(int p, int q){
  int op = 0;
  word_t val1 = 0;
  word_t val2 = 0;
  word_t val3 = 1;
  
  if (p > q) {
    /* Bad expression */
    return 1;
  }
  else if (p == q) {
    /* Single token.
     * For now this token should be a number.
     * Return the value of the number.
     */
    bool success = false;
    if(tokens[p].type == TK_number){
      sscanf(tokens[p].str, "%ld", &val3);
    }
    else if(tokens[p].type == TK_hex){
      sscanf(tokens[p].str, "%lx", &val3);
    }
    else if(tokens[p].type == TK_reg){
      val3 = isa_reg_str2val(tokens[p].str, &success);
      //printf("val3 = %ld\n", val3);
    }
    return val3;
    //printf("%s", tokens[p].str);
    //return 666;
  }
  else if (check_parentheses(p, q) == true) {
    /* The expression is surrounded by a matched pair of parentheses.
     * If that is the case, just throw away the parentheses.
     */
    //printf("check  p=%d,q=%d\n", p, q);
    return eval(p + 1, q - 1);
  }
  else {
    op = dominant_operator( p , q );
    //printf("...\n");
    //printf("p=%d, q=%d, op=%d\n", p, q, op);
    val1 = eval(p, op - 1);
    val2 = eval(op + 1, q);
    //printf("val1=%d, val2=%d, op=%d\n", val1, val2, op);
    //printf("tokens[op].type = %d", tokens[op].type);
    switch (tokens[op].type) {
      case '+': return val1 + val2;
      case '-': return val1 - val2;/* ... */
      case '*': return val1 * val2;/* ... */
      case '/': return val1 / val2;/* ... */
      case NEG: return val2 * (-1);
      case DEREF: return paddr_read(val2 , 4);
      //case DEREF: return isa_reg_str2val( val2, )
      default: assert(0);return 0;
    }
  }
}


                              

word_t expr(char *e, bool *success) {
  if (!make_token(e)) {
    *success = false;
    return 1;
  }else{
    *success = true;
    //printf("nr_token = %d\n", nr_token);
    return eval(0, nr_token);
    //return nr_token;
  }
}
